home *** CD-ROM | disk | FTP | other *** search
/ Aminet 21 / Aminet 21 (1997)(GTI - Schatztruhe)[!][Oct 1997].iso / Aminet / dev / c / BinaryTrees.readme < prev    next >
Encoding:
Text File  |  1997-09-05  |  1.7 KB  |  41 lines
  1. Short:    Binary AVL & Splay trees non-recursive.
  2. Author:   crh@ubiqx.mn.org (Christopher R. Hertel)
  3. Uploader: crh@ubiqx.mn.org (Christopher R. Hertel)
  4. Version:  2.4.
  5. Type:     dev/c
  6.  
  7. Written in C using OOP techniques, these modules provide three forms of
  8. binary tree: Simple (unbalanced) AVL (height-balanced), and Splay.  AVL
  9. trees are re-balanced after every insertion or deletion.  For each node in
  10. the tree, the difference in height between the left and right subtree is
  11. at most 1.  Splay trees use a different approach.  Each time a node is
  12. accessed (inserted, deleted, or directly found via a search), the node is
  13. bubbled to the top of the tree.  This has the effect of making the tree
  14. 'bushier' and placing the most frequently accessed nodes nearer to the
  15. top.
  16.  
  17. The functions are non-recursive to limit stack space usage, and can also
  18. be made into a run-time library.  The type of tree used is determined by
  19. which header file is included with your program.  No other code changes
  20. are necessary.
  21.  
  22. Pretty darn fast, too, IMHO. 
  23.  
  24. Chris Hertel
  25.  
  26.  
  27. ============================= Archive contents =============================
  28.  
  29. Original  Packed Ratio    Date     Time    Name
  30. -------- ------- ----- --------- --------  -------------
  31.     1038     581 44.0% 06-Aug-97 13:45:10  BinaryTrees.readme
  32.    27943    7334 73.7% 26-Jul-97 00:20:12  ubi_AVLtree.c
  33.    15982    5091 68.1% 26-Jul-97 00:20:18  ubi_AVLtree.h
  34.    42918   11362 73.5% 26-Jul-97 00:20:32  ubi_BinTree.c
  35.    35348    9211 73.9% 26-Jul-97 00:20:46  ubi_BinTree.h
  36.    19641    5910 69.9% 26-Jul-97 00:20:54  ubi_SplayTree.c
  37.    15650    4866 68.9% 26-Jul-97 00:21:00  ubi_SplayTree.h
  38.     9245    2664 71.1% 26-Jul-97 00:21:04  ubi_sample.c
  39. -------- ------- ----- --------- --------
  40.   167765   47019 71.9% 07-Aug-97 08:32:04   8 files
  41.